package com.tree;

import java.util.ArrayList;

import java.util.Comparator;
import java.util.List;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: HuffmanTree
 * @description: 赫夫曼树
 * @date 2021/3/2614:33
 * @since V1.0
 */
public class HuffmanTree {
    public static void main(String[] args) {
        //int[] arr = new int[]{5,15,40,30,10};
        int[] arr = new int[]{9,5,4,2};
        fun(arr);

    }

    public static void fun(int[] arr){
        if (arr.length<2) return;
        ArrayList<HeroNode> list = new ArrayList<>();
        for (int item:arr){
            HeroNode heroNode = new HeroNode(item, ""+item);
            list.add(heroNode);
        }
        HeroNode huffman = huffman(list);
        huffman.preOrder();
    }

    public static HeroNode huffman(List<HeroNode> list){
        if (list.size()==2){
            HeroNode root = new HeroNode();
            root.setId(list.get(0).getId()+list.get(1).getId());
            root.leftNode = list.get(0);
            root.rightNode = list.get(1);
            return root;
        }
        //根据id排序
        list.sort(Comparator.comparing(o -> o.getId()));
        HeroNode heroNode = new HeroNode();
        heroNode.setId(list.get(0).getId()+list.get(1).getId());
        heroNode.leftNode = list.get(0);
        heroNode.rightNode = list.get(1);
        list.remove(0);
        list.remove(0);
        list.add(heroNode);
        return huffman(list);
    }
}
